import heapq
from typing import List


class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])

        # 左上到右下的前缀和
        prefix1 = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                prefix1[i][j] = prefix1[i - 1][j - 1] + grid[i - 1][j - 1]

        # print("左上到右下的前缀和:")
        # for row in prefix1:
        #     print(row)

        # 右上到左下的前缀和
        prefix2 = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(n - 1, -1, -1):
                prefix2[i][j] = prefix2[i - 1][j + 1] + grid[i - 1][j]

        # print("右上到左下的前缀和:")
        # for row in prefix2:
        #     print(row)

        # 遍历以每个位置为菱形下方的点的所有可能的结果
        ans = []
        for i in range(m):
            for j in range(n):
                # 计算菱形的最大尺寸
                num = min(i // 2, j, n - j - 1) + 1

                # 遍历所有可能的菱形尺寸
                for k in range(num):
                    if k == 0:
                        res = grid[i][j]
                    else:
                        # 下端点：grid[i][j] ; prefix1[i+1][j+1] ; prefix2[i+1][j]
                        # 左端点：grid[i-k][j-k] ; prefix1[i-k+1][j-k+1] ; prefix2[i-k+1][j-k]
                        # 右端点：grid[i-k][j+k] ; prefix1[i-k+1][j+k+1] ; prefix2[i-k+1][j+k]
                        # 上端点：grid[i-2k][j] ; prefix1[i-2k+1][j+1] ; prefix2[i-2k+1][j]
                        res = (prefix1[i + 1][j + 1] - prefix1[i - k][j - k] +  # 左下（包含两端点）
                               prefix2[i + 1][j] - prefix2[i - k][j + k + 1] +  # 右下（包含两端点）
                               prefix1[i - k + 1][j + k + 1] - prefix1[i - 2 * k][j] +  # 右上（包含两端点）
                               prefix2[i - k + 1][j - k] - prefix2[i - 2 * k][j + 1])  # 左上（包含两端点）
                        res -= grid[i][j] + grid[i - k][j - k] + grid[i - k][j + k] + grid[i - 2 * k][j]  # 减去4个端点
                        # print(i, j, k, ":", res,
                        #       prefix1[i + 1][j + 1] - prefix1[i - k][j - k],
                        #       prefix2[i + 1][j] - prefix2[i - k][j + k + 1],
                        #       prefix1[i - k + 1][j + k + 1] - prefix1[i - 2 * k][j],
                        #       prefix2[i - k + 1][j - k] - prefix2[i - 2 * k][j - 1])

                    if len(ans) < 3:
                        if res not in ans:
                            heapq.heappush(ans, res)
                    else:
                        if res not in ans:
                            heapq.heappushpop(ans, res)

        ans.sort(reverse=True)
        return ans


if __name__ == "__main__":
    # [228,216,211]
    print(Solution().getBiggestThree(grid=[[3, 4, 5, 1, 3],
                                           [3, 3, 4, 2, 3],
                                           [20, 30, 200, 40, 10],
                                           [1, 5, 5, 4, 1],
                                           [4, 3, 2, 2, 5]]))

    print(Solution().getBiggestThree(grid=[[1, 2, 3],
                                           [4, 5, 6],
                                           [7, 8, 9]]))
    print(Solution().getBiggestThree(grid=[[7, 7, 7]]))
